// ALERT: 本代码中涉及的树,一定是按层次建立的二叉树。

#include <stdio.h>
#include <stdlib.h>

#include "function.h"

// FUNCTION: 先序遍历（递归实现）
// abdhiejcfg
void preOrder(BiTree p) {
	if (p != NULL) {
		putchar(p->c);//等价于visit函数
		preOrder(p->lchild);
		preOrder(p->rchild);
	}
}

// FUNCTION: 中序遍历（递归实现）
// hdibjeafcg
void InOrder(BiTree p) {
	if (p != NULL) {
		InOrder(p->lchild);
		putchar(p->c);
		InOrder(p->rchild);
	}
}

// FUNCTION: 后序遍历（递归实现）
// hidjebfgca
void PostOrder(BiTree p) {
	if (p != NULL) {
		PostOrder(p->lchild);
		PostOrder(p->rchild);
		putchar(p->c);
	}
}

// FUNCTION: 中序遍历非递归，非递归执行效率更高，考的概率很低
void InOrder_Non_Recursion(BiTree T) {
	// NOTE: 声明顺序栈变量S
	SqStack S;


	// NOTE: 初始化过程
	// STEP: 栈初始化
	InitStack(S);

	// STEP: 遍历指针p初始化——指向树T的树根
	BiTree p = T;


	// NOTE: 元素入栈
	while (p || !StackEmpty(S)) {
		if (p) {
			Push(S, p);
			p = p->lchild;
		} else {
			Pop(S, p);
			putchar(p->c);
			p = p->rchild;
		}
	}
}


// FUNCTION: 前序遍历非递归，非递归执行效率更高，考的概率很低
void PreOrder_Non_Recursion(BiTree T) {
	// NOTE: 声明顺序栈变量S
	SqStack S;


	// NOTE: 初始化过程
	// STEP: 栈初始化
	InitStack(S);

	// STEP: 遍历指针p初始化——指向树T的树根
	BiTree p = T;


	// NOTE: 元素入栈
	while (p || !StackEmpty(S)) {
		if (p) {
			putchar(p->c);
			Push(S, p);
			p = p->lchild;
		} else {
			Pop(S, p);
			p = p->rchild;
		}
	}
}


// FUNCTION: 后序遍历非递归，非递归执行效率更高，考的概率很低
void PostOrder_Non_Recursion(BiTree T) {
	// NOTE: 声明顺序栈变量S
	SqStack S;


	// NOTE: 初始化过程
	// STEP: 栈初始化
	InitStack(S);

	// STEP: 遍历指针p初始化——指向树T的树根
	BiTree p = T;

	// STEP: 记录最近访问过的结点r
	BiTree r = NULL;


	// NOTE: 元素入栈
	while (p || !StackEmpty(S)) {
		if (p) {
			Push(S, p);
			p = p->lchild;
		} else {
			// 读栈顶结点（非出栈）
			GetTop(S, p);
			// 若右子树存在，且未被访问过，转向右
			if (p->rchild && p->rchild != r) {
				p = p->rchild;
			} else {
				// 将结点弹出栈
				Pop(S, p);
				// 访问该结点
				putchar(p->c);
				// 记录最近访问过的结点
				r = p;
				// 结点访问完后，重置P指针
				p = NULL;
			}
		}
	}
}


// FUNCTION: 层次遍历——又名：广度优先遍历
void LevelOrder(BiTree T) {
	// NOTE: 声明顺序队列变量S
	LinkQueue Q;

	// NOTE: 初始化过程
	// STEP: 队列初始化
	InitQueue(Q);
	// STEP: 遍历指针p初始化
	BiTree p;


	// NOTE: 开始遍历
	// STEP: 树根入队
	EnQueue(Q, T);

	// STEP: 后续结点的遍历
	while (!IsEmpty(Q)) {
		// 队首元素出队
		DeQueue(Q, p);

		// 访问该结点
		putchar(p->c);

		// 该结点的左孩子入队（若存在）
		if (p->lchild != NULL) {
			EnQueue(Q, p->lchild);
		}

		// 该结点的有孩子入队（若存在）
		if (p->rchild != NULL) {
			EnQueue(Q, p->rchild);
		}
	}
}


int main() {
	setbuf(stdout, NULL);

	// NOTE: Variable declaration
	// STEP: 结构体指针变量——指向临时创建的结点
	BiTree pnew;
	int i, j, pos;
	char c;


	// NOTE: 定义树根结点
	BiTree tree = NULL;


	// NOTE: 建队辅助队列
	// HINT: phead就是队头指针，ptail就是队尾指针
	ptag_t phead = NULL, ptail = NULL, listpnew = NULL, pcur = NULL;


	// NOTE: 建树相关过程>>>输入样例数据：abcdefghij、123456789
	do {
		// NOTE: 获取用户输入
		printf("Please input: ");
		scanf("%c", &c);


		// NOTE: 循环退出条件
		if (c == '\n') {
			break;
		}


		// NOTE: 申请空间
		// STEP: 申请树结点
		// HINT: calloc申请的空间，会自动写0初始化
		pnew = (BiTree) calloc(1, sizeof(BiTNode));

		// STEP: 向树结点赋值数据
		pnew->c = c;

		// STEP: 申请队列结点
		listpnew = (ptag_t) calloc(1, sizeof(tag_t));

		// STEP: 队列结点赋值数据——让新队列结点指向新树结点
		listpnew->p = pnew;


		// NOTE: 构建辅助队列
		if (NULL == tree) {
			// HINT: 树为空树时，特别处理维护辅助队列的过程

			// STEP: 树的根
			tree = pnew;

			// STEP: 队头指针和队尾指针指向listpnew
			phead = ptail = listpnew;

			// STEP: pcur始终指向要插入的结点的位置
			pcur = listpnew;

			// STEP: 强制进入下一轮循环
			continue;
		} else {
			// HINT: 树不为空时，维护辅助队列的过程

			// STEP:新结点放入链表（尾插法）
			ptail->pnext = listpnew;

			// STEP:ptail指向队列尾部
			ptail = listpnew;
		}


		// NOTE: 构建树
		if (NULL == pcur->p->lchild) {
			// REVIEW: 把新结点pnew放到要目标结点pcur的左边
			pcur->p->lchild = pnew;
		} else if (NULL == pcur->p->rchild) {
			// REVIEW: 把新结点pnew放到要目标结点pcur的右边
			pcur->p->rchild = pnew;

			// ALERT: 左右都放了结点后，pcur指向队列的下一个
			pcur = pcur->pnext;
		}
	} while (c != EOF);

	printf("--------前序遍历----------\n");
	preOrder(tree);

	printf("\n--------中序遍历------------\n");
	InOrder(tree);

	printf("\n--------后序遍历------------\n");
	PostOrder(tree);

	printf("\n--------中序遍历（非递归实现）------\n");
	InOrder_Non_Recursion(tree);

	printf("\n--------层次遍历-----------\n");
	LevelOrder(tree);
	printf("\n");

	return 0;
}

// THINKING: [总结]层次建树的实现逻辑。
//  需要定义两类结构体：①用于构建树的（BiTNode）②用于构建队列的（tag）。
//  当程序运行时，程序起初会默认创建一个指针tree，作为树根指针；默认创建phead、ptail、listpnew、pcur，用于维护和操作辅助队列。
//  在初始化工作完成后，程序进入循环。每轮循环会从先键盘标准输入流中读取一个字符，并判断字符是否为回车？一经检测是回车，自动结束循环。
//  当程序通过检测后，正式进入建树的过程。这个过程分为3步。（建树前的结点准备工作、维护辅助队列、建树）
//    首先，申请空间（执行建树前的结点准备工作）。此步骤包含4小项：
//      ①创建新树结点，并用pnew指向；
//      ②新树结点赋值（将用户的输入，写入新树结点的数据域c中。）；
//      ③创建新队列结点，并用listpnew指向；
//      ④新队列结点赋值（将pnew指向的地址，写入队列结点的数据域中。）
//    然后，维护辅助队列。维护辅助队列的过程需要区分待插结点的插入位置——是否往树根处插？
//      如果是：
//        ①让树根指针指向pnew所指结点；
//        ②让队列元素入队。此处需初始化队头指针phead和队尾指针ptail，使之指向listpnew所指结点；
//        ③pcur指向listpnew所指结点【这里需要注意的是：pcur始终指向需操作树结点。此所谓需操作是指，需要将新树结点往该目标结点的左或右孩子插入的树结点。】
//        ④强制让循环进入下一轮。
//      如果不是：
//        ①让队列元素入队。此处仅需用队列操作的尾插法，将结点串入队列中；
//        ②重新维护队尾指针的指向。
//    最后，建树。【在讲解建树前，不妨先简述一下其中的原理。pcur和listpnew，实际上是单链表结点。每个结点可以存储树的某个结点的地址值，以及指向自身结构体类型的指针域。有这样的数据结构就可以构建一个单链表结构的辅助队列了。根据上述过程可知，每轮循环会向辅助队列的队尾插入一个新结点。而pcur指针的赋值在第一轮循环完成。所以，进入第二轮循环后，pcur的指向恰号是树根结点。所以，每次只需判断当前pcur的所指结点pcur->p的左或右孩子是否为空？按照“先左后右、为空必插”原则，插入新树结点pnew。所以，当pcur->p的左孩子为空时，使之直接指向pnew所指结点即可；但，当pcur->p的右孩子为空时，需注意，在使之指向pnew所指结点后，还需重新确定pcur的指向。（即队列中，pcur的后继结点——pcur->pnext）。故如此往复，二叉树的层序建树就完成了。】

// FIXME: 此代码还可以扩展。比方说：二叉树的构建可以根据前序和中序遍历序列，或后序和中序遍历序列来建树。这两种方法同样可以实现对二叉树的建立。